1. Field of Invention
The present invention relates to an encryption technique as an information security technique, and particularly to an encryption which does not cause decryption failure.
2. Description of the Related Art
Encrypted communication using a public key cryptosystem is suggested as a conventional method to realize confidential communications between a transmission apparatus and a receiving apparatus. To briefly describe the conventional encrypted communication, the transmission apparatus encrypts the contents of the communication using a public key of the receiving apparatus and transmits it, and the receiving apparatus receives the encrypted contents and obtains the original contents by decrypting it with its own private key (e.g. See Non-Patent Literature 1). It is difficult to calculate a value indicative of the private key from a value indicative of the public key. The general encrypted communication system using this method is configured by plural transmission apparatuses and receiving apparatuses. A transmission apparatus firstly acquires a public key of a partner receiving apparatus. This public key pairs with the private key possessed by the partner receiving apparatus and is made public in the system. Then, the transmission apparatus encrypts the data to be communicated, using the public key obtained in the above manner and transmits it, whereas the receiving apparatus receives such encrypted communication data, decrypts the data using its own private key so as to obtain the original data.
In 1996, an NTRU (a trademark of NTRU cryptosystems, Inc.) cryptosystem was proposed as a public key cryptosystem capable of high-speed processing (e.g. See Non-Patent Literature 2). In the NTRU cryptosystem, encryption and decryption are performed using polynomial operations which enable computation at a speed higher than the speed achieved in RSA (Rivest Shamir Adleman) cryptosystem, in which modulo exponentiation is performed in certain modulo, as well as in an elliptic-curve cryptosystem in which scalar multiplications are performed on points on an elliptic curve. It is therefore possible to perform processing at a higher speed than in the case of the existing public key cryptosystems, and thereby to perform encryption and decryption within a practical period of time even through software processing.
Thus, the encrypted communication system using the NTRU cryptosystem as a public key cryptosystem has an advantage that processing between a transmission apparatus and a receiving apparatus can be performed at a higher speed than in the case of the encrypted communication system using the existing public key cryptosystem.
The NTRU cryptosystem is described in detail in Non-Patent Literature 2, so that no detailed description is given here but a brief one will be provided below.
<NTRU Cryptosystem>
(1) NTRU Parameters
The NTRU cryptosystem uses non-negative integer parameters N, p, q, df, dg and d. The following describes the meanings of these parameters.
(i) Parameter N
The NTRU cryptosystem is a public-key cryptosystem for performing encryption and decryption by performing polynomial operations. The degree of polynomials used in the NTRU cryptosystem is determined by a parameter N mentioned above.
Polynomials used in the NTRU cryptosystem are integer coefficient polynomials of degree (N−1) or lower with respect to the parameter N. When N=5, for example, a polynomial may be expressed by X^4+X^3+1, and the like. Here, “X^a” shall denote the “a” th power of X. Moreover, a public key h, a private key f, a plain text m, a random number r, and an encrypted text c used for encryption or decryption are each represented by a polynomial of degree (N−1) or lower.
A polynomial is computed so that the result of a computation always gives a polynomial of degree (N−1) or lower, using the relational expression “X^N=1” with respect to the parameter N. When N=5, for example, assuming that“x” denotes a product of a polynomial and a polynomial and that “·” denotes a product of an integer and a polynomial (or a product of an integer and an integer), a polynomial of degree (N−1) or lower can be always derived, as follows, as a product of the polynomial X^4+X^2+1 and the polynomial X^3+X, using the relational expression “X^5=1”:
                                          (                                          X                ^                4                            +                              X                ^                2                            +              1                        )                    ×                      (                                          X                ^                3                            +              X                        )                          =                              X            ^            7                    +                      2            ·                          X              ^              5                                +                      2            ·                          X              ^              3                                +          X                                        =                                            X              ^              2                        ×            1                    +                      2            ·            1                    +                      2            ·                          X              ^              3                                +          X                                        =                              2            ·                          X              ^              3                                +                      X            ^            2                    +          X          +          2.                    
(ii) Parameters p and q
An NTRU cryptosystem uses parameters p and q which are integers of 2 or greater. The coefficients in a polynomial that appears in the NTRU cryptosystem obtain remainder modulo p and q. As is described in Non-Patent Literature 2, these parameters p and q must be relatively prime.
(iii) Parameters df, dg, and d
The selection of a polynomial f that is a part of the private key handled in the NTRU cryptosystem, a polynomial g that is used together with the polynomial f at the time of generating a public key polynomial h, and a random number polynomial r used for encrypting a plain text, depends on the respective parameters df, dg, and d.
First, a polynomial f is selected so that df coefficients indicate “1”, (df−1) coefficients indicate “−1”, and the other coefficients indicate “0”. In other words, a polynomial f is a polynomial of degree (N−1) or lower having N coefficients ranged from coefficients of degree 0 (constant term) to degree (N−1). A polynomial f is selected so that df coefficients indicate “1”, (df−1) coefficients indicate “−1”, and (N−2df+1) coefficients indicate “0” out of the above N coefficients.
Then, a polynomial g is selected so that dg coefficients indicate “1”, dg coefficients indicate “−1”, and the other coefficients indicate “0”. Furthermore, a random number polynomial r is selected so that d coefficients indicate “1”, d coefficients indicate “−1”, and the other coefficients indicate “0”.
The following are three examples of NTRU parameters presented in Non-Patent Literature 2: (N, p, q, df, dg, d)=(107, 3, 64, 15, 12, 5); (N, p, q, df, dg, d)=(167, 3, 128, 61, 20, 18); and (N, p, q, df, dg, d)=(503, 3, 256, 216, 72, 55).
(2) Key Generation in NTRU Cryptosystem
As described above, the respective polynomials f and g are generated at random using the parameters df and dg in the NTRU cryptosystem. As described in Non-Patent Literature 2, a polynomial h is generated by the expressionh=Fq×g(mod q),using a polynomial Fq having a relationship expressed by Fq×f=1(mod q). Here, a(mod b) denotes remainder obtained when a is divided by b.
In the NTRU cryptosystem, (f, Fp) denotes a private key and h denotes a public key.
The expression “x=y(mod q)” is an operation which derives, as the coefficient of i-th degree in a polynomial x, remainder obtained when the coefficient of i-th degree in a polynomial y is divided by modulo q so that the remainder indicates a value ranged from “0” to “q−1” (0≦i≦N−1). That is to say that it is an operation which derives, as a polynomial x, a polynomial to which a mod q operation (an operation to derive remainder when divided by modulo q, a remainder operation of modulo q) is executed so that each of the coefficients in the polynomial y indicate a value ranged from “0” to “(q−1)”.
(3) Encryption in NTRU Cryptosystem
In the encryption based on the NTRU cryptosystem, a polynomial m being a plain text is encrypted and a polynomial c being an encrypted text is calculated. First, a random number r which is the polynomial as described above is generated at random. In other words, a random number r is a polynomial of degree (N−1) or lower, and has N coefficients of degree 0 (constant term) to degree (N−1). A polynomial (random number) r is randomly selected so that d coefficients indicate “1”, d coefficients indicate “−1” and (N−2d) coefficients indicate “0” out of the N coefficients.
Then, an encrypted text c is generated, with respect to the plain text m of (N−1) degree or lower whose coefficients indicate 0, 1 or −1, by the expression indicated below, using the random number r and the public key h, wherec=p·r×h+m(mod q).
As has been described above, this operation is an operation which derives, as a polynomial c, a polynomial to which the mod q operation is performed so that each of the coefficients in the polynomial (p·r×h+m) indicates a value ranged from “0” to “(q−1)”.
(4) Decryption in NTRU Cryptosystem
In the decryption based on the NTRU cryptosystem, a polynomial c which is an encrypted text is decrypted, and a polynomial m′ which is a decrypted text is calculated. At the time of decryption, a polynomial a is firstly calculated, with respect to the encrypted text c, by the expression indicated below using a polynomial f which constitutes a part of the private key, wherea=f×c(mod q*).
Here, “(mod q*)” is different from the (mod q) operation described above, and is an operation which obtains, as the coefficient of the i-th (0≦i≦N−1) degree in the polynomial a, remainder obtained when the coefficient of the i-th degree in the polynomial (f×c) is divided by modulo q so that the remainder indicates a value ranged from “<−q/2>+1” to “<q/2>”. In other words, in the case where the coefficient indicates a value ranged from “<q−2>” to “q−1”, q is subtracted from the coefficient so that the coefficient is adjusted to indicate the value within the above range. Here, <x> indicates the largest number among the numbers indicating x and lower, and may be expressed by <−1/2>=−1, for example.
Next, a polynomial b is generated with respect to the polynomial a by the expression indicated below using a parameter p, whereb=a(mod p).
Then, a decrypted text m′ is calculated with respect to the polynomial b by the following expression using a polynomial Fp which is a part of the private key, wherem′=Fp×b(mod p*).
Note that, as described above, the operation (mod p*) is an operation which obtains, as the coefficient of i-th degree in the polynomial m′, remainder obtained when the coefficient of i-th degree in the polynomial (Fp×b) is divided by modulo p so that the remainder indicates a value ranged from “<−p/2>+1” to “<p/2>”.
With regard to the NTRU cryptosystem, all of the above-mentioned parameters are to satisfy p=3, but the parameters which satisfy p=2 are also disclosed (see e.g. Non-Patent Literature 3). However, as is described in Non-Patent Literature 2, in the case of p=3, the plain text m is a polynomial whose coefficients indicate one of the three values 0, 1 and −1, whereas in the case of p=2, the plain text m is a polynomial whose coefficients indicate one of the two values 0 and 1. The private key polynomials f and g and the random number r are polynomials whose coefficients indicate one of the three values 0, 1 and −1, regardless of whether p=2 or p=3.
As a key generation method based on the NTRU cryptosystem, the method for generating a public key h so as to satisfy the expressionh=p·Fq×g(mod q),and performing encryption using the expressionc=r×h+m(mod q),is also disclosed (see e.g. Non-Patent Literature 5)
However, there is a problem with such NTRU cryptosystem as described above that a decrypted text is different from an original plain text even when an encrypted text is generated by encrypting the plain text with a public key, and the decrypted text is generated by decrypting such encrypted text with a valid private key (see e.g. Non-Patent Literature 2). This is referred to an expression that goes “a decryption error (failure) occurs”. According to the NTRU cryptosystem described in Non-Patent Literature 2, the decryption failure probability depends on how the parameters are derived, however, it is known that the decryption failure probability is about 10^(−5) for any of the parameters disclosed in the above-cited reference (see e.g. Non-Patent Literature 3).
In contrast, recently a method called NTRUEncrypt scheme which is a new NTRU cryptosystem that reduces the decryption failure probability to 2^(−100) by restricting the parameters to the parameters to be mentioned later and adding calculations which reduce such probability in decryption (see e.g. Non-Patent Literature 4).
As the NTRUEncrypt scheme is described in detail in Non-Patent Literature 4, the detailed description is not given here but the brief one will follow.
<NTRUEncrypt Scheme>
(1) NTRUEncrypt Parameters
The NTRUEncrypt scheme uses non-negative integer parameters N, p, q, df, dg, and d. According to Non-Patent Literature 4, only the parameters expressed as (N, p, q, df, dg, d)=(251, 2, 239, 72, 72, 72) are disclosed as NTRUEncrypt parameters. Among the parameters used in the NTRUEncrypt scheme, the meanings of the parameters df, dg and d are different from the meanings of the parameters used in the NTRU cryptosystem.
The following describes the meanings of such parameters focusing on the difference between the NTRUEncrypt parameters and the parameters used in the NTRU cryptosystem.
(i) Parameter N
As described above, the NTRUEncrypt scheme, like the NTRU cryptosystem, is a public key cryptosystem which performs encryption and decryption by performing polynomial operations. As is the case of the NTRU cryptosystem, a polynomial handled in the NTRUEncrypt scheme is an integer coefficient polynomial of degree (N−1) or lower with respect to the parameter N, and a polynomial operation is performed using the relational expression X^N=1 so that a polynomial of degree (N−1) or lower is always derived as the result of the operation.
(ii) Parameters p and q
As is described above, the NTRUEncrypt uses the parameters p and q defined as p=2 and q=239. Such parameters p and q are relatively prime.
(iii) Parameters df, dg and d
How to select a polynomial f which is a part of the private key handled in the NTRUEncrypt, a polynomial g which is used together with the polynomial f in the generation of a public key polynomial h, and a random number polynomial r to be used for encrypting a plain text depends on the respective parameters df, dg and d.
First, a polynomial f of degree (N−1) or lower whose df coefficients indicate 1 and the other coefficients indicate 0 is selected.
Then, a polynomial of degree (N−1) or lower whose dg coefficients indicate 1 and the other coefficients indicate 0 is selected. Similarly, a polynomial of degree (N−1) or lower whose d coefficients indicate 1 and the other coefficients indicate 0 is selected as the random number r.
In other words, the difference between the NTRU cryptosystem and the NTRUEncrypt scheme is that in the NTRU cryptosystem, the polynomial whose coefficients indicate 0, 1 or −1 is selected for the polynomials f, g and r, whereas in the NTRUEncrypt scheme, the polynomial whose coefficients indicate 0 or 1 is selected for the polynomials f, g and r.
(2) Key Generation in NTRUEncrypt
As described above, in the NTRUEncrypt scheme, the polynomials f and g are generated at random using the parameters df and dg. As is described in Non-Patent Literature 4, the polynomial h is generated by the expressionh=p·Fq×g(mod q),using the polynomial Fq which satisfies Fq×f=1(mod q). The NTRUEncrypt scheme defines that (f, Fp) denotes a private key and a polynomial h denotes a public key.
(3) Encryption in NTRUEncrypt Scheme
In the NTRUEncrypt scheme, the random number r as described above is firstly generated. That is to say that a polynomial of degree (N−1) or lower whose d coefficients indicate 1 and the other coefficients indicate 0 is randomly selected, using the parameter d, as the random number r.
Then, an encrypted text c is generated, with respect to a plain text m of degree (N−1) or lower by the expressionc=r×h+m(mod q),
whose coefficients indicate 0 or 1, using the random number r and the public key h.
As described above, this operation is an operation where the polynomial c is a polynomial to which the mod q operation is performed so that each of the coefficients in the polynomial (r×h+m) indicates a value ranged from “0” to “(q−1)”.
Note that there is no essential difference between the NTRU cryptosystem and the NTRUEncrypt scheme since a value of the encrypted text c indicates the same value as derived in the case of NTRU cryptosystem even in the case where a public key h is generated so as to satisfy h=Fq×g(mod q) in the key generation processing, and the encryption is performed using the expressionc=p·r×h+m(mod q).
(4) Decryption in NTRUEncrypt Scheme
In decryption, a polynomial a is calculated with respect to the encrypted text c by the expression a=f×c(mod q**) using a polynomial f which is a part of the private key.
Here, (mod q**) operation is different from the above-mentioned (mod q) operation, and is an operation which obtains, as the coefficient of i-th degree in the polynomial a, remainder obtained when the coefficient of i-th degree in the polynomial (f×c) is divided by modulo q so that the remainder indicates a value located within an appropriate section of width q. The operation method is defined in detail by an algorithm called center1 or center2 described in Non-Patent Literature 4.
The algorithm center2 is described below.
(Algorithm Center 2)
Step 1: Calculation is performed using I1=(A(1)−p×d×dg)/(df^(−1) mod q) mod q, where A=f×c(mod q). Here, A(1) denotes a value derived when 1 is substituted into a variable x of the polynomial A.
Step 2: I2 shall be defined as a value obtained when an adjustment is made by adding a multiple of q to I1 so that I1 indicates a value ranged from “<(N−q)/2>+1” to “<(N+q)/2)” (I2=I1 mod q is surely satisfied).
Step 3: Calculation is performed using J=df×I2+p×d×dg.
Step 4: A polynomial after the adjustment of adding a multiple of q to each coefficient so that each of the coefficients in the polynomial A indicates a value ranged from “<J/N−q/2>+1” to “<J/N+q/2>” is assumed to be a polynomial a(=f×c(mod q**)).
This operation is performed for reducing the decryption failure probability.
Next, a polynomial b is generated with respect to the polynomial a by the expression b=a(mod p), using a parameter p.
Then, a decrypted text m′ is generated with respect to the polynomial b by the expression m′=Fp×b(mod p) using a polynomial Fp which is a part of the private key.
Note that, as to the NTRUEncrypt scheme, a method of selecting a polynomial F of degree (N−1) or lower whose df coefficients indicate 1 and the other coefficients indicate 0, and then constituting a polynomial f by the expression f=1+p·F (see e.g. Non-Patent Literature 4). As described in Non-Patent Literature 4, this method does not require polynomial multiplication to be performed between the polynomial f and the polynomial Fp in the decryption processing, since the polynomial Fp which satisfies Fp×f=1(mod p) is expressed by Fp=1(mod p) due to the polynomial f expressed as in the expression f=1+p·F, and a decrypted text m′ can be generated by the expression m′=a(mod p).
The NTRUEncrypt scheme is a method which reduces the occurrence of decryption failure more than the NTRU cryptosystem, by performing, in the decryption, processing for reducing the decryption failure probability. Nevertheless, such NTRUEncrypt scheme merely indicates that the decryption failure probability is 2^(−100) or lower, and the method enabling the probability to be 0, namely, the method of completely eliminating decryption failure is not known.
Note that both the NTRU cryptosystem and the NTRUEncrypt scheme express an operation using a polynomial, however, Patent Reference 1 expresses a polynomial as elements in a general ring R. To be more precise, the above-mentioned polynomials are described as the elements in the ring R whereas the parameters p and q are presented as ideals of the ring R.
Patent Reference 1: Japanese Unexamined Patent Publication No. 2000-516733.
Non-Patent Literature 1: Modern Cryptography, Mathematics in Information Science. Ser. Tatsuaki Okamoto, and Hirosuke Yamamoto, Sangyo Tosho, 1997.
Non-Patent Literature 2: Jeffery Hoffstein, Jill Pipher, and Joseph H. Silverman, “NTRU: A ring based public key cryptosystem”, Lecture Notes in Computer Science, 1423, pp. 267-288, Springer-Verlag, 1998.
Non-Patent Literature 3: Joseph H. Silverman, “NTRU Cryptosystems Technical Report #011, Version 2, Wraps, Gaps, and Lattice Constants”, [online], Mar. 15, 2001, [searched on Dec. 15, 2003], Internet <URL: http://www.ntru.com/cryptolab/pdf/NTRUTech011_v2.pdf>.
Non-Patent Literature 4: Joseph H. Silverman, W. Whyte, “NTRU Cryptosystems Technical Report #018, Version 1, Estimating Decryption Failure Probabilities for NTRUEncrypt”, [online], 2003, [searched on Dec. 15, 2003], Internet <URL: http://www.ntru.com/cryptolab/pdf/NTRUTech018.pdf>.
Non-Patent Literature 5: “NTRU Cryptosystems, Inc., “The NTRU Public Key Cryptosystem—A Tutorial”, [online], [searched on Dec. 15, 2003], Internet <URL: http://www.ntru.com/cryptolab/pdf/ntrututorials.pdf>.
Non-Patent Literature 6: Nick Howgrave—Graham, Joseph H. Silverman, and William Whyte, “NTRU Cryptosystems Technical Report #004, Version 2, A Meet-In-The-Middle Attack on an NTRU Private Key”, [online], 2003, [searched on Dec. 15, 2003], Internet <URL: http://www.ntru.com/cryptolab/pdf/NTRUech018.pdf>“The NTRU Public Key Cryptosystem—A Tutorial”, [online], [searched on Dec. 15, 2003], Internet <URL: http//www.ntru.com/cryptolab/pdf/NTRUTech004v2.pdf>.
Non-Patent Literature 7: Jeffery Hoffstein, Joseph H. Silverman, and William Whyte, “NTRU Cryptosystems Technical Report #012, Version 2, Estimated Breaking Times for NTRU Lattices”, [online], 2003, [searched on Dec. 15, 2003], Internet <URL: http://www/ntru.com/cryptola b/pdf/NTRUTech012v2.pdf>.